package 动态规划;

/**
 * 完全背包问题迭代解法：
 *  迭代思路：
 *      当有 nums.length 个物品，物品的重量为nums.w,价值为nums.c
 *          假设有两个物品 重量 分别为 1,2 价值分别为 2,5
 *      f(n)表示容量为n时，在这些商品中最多能取到的的值
 *      f(1): 判断 容量为1时是否能拿 nums[1],nums[2],...,nums[length]
 *          如果能拿，那么通过比较 拿nums[1] f(1-nums[1])的最大值，拿nums[2] f(1-nums[2])的最大值,...,拿nums[length] f(1-nums[length])的最大值
 *          这里的f(1-nums[n].w)表示容量刚好可以放下 nums[n]的重量
 *
 *      f(2): 判断容量为2时是否能拿 nums[1],nums[2],...,nums[length]然后选择 最大的一件
 */
public class Ch07_完全背包问题迭代 {
    public static void main(String[] args) {
//        int[] w={7,3,4,2};   //重量
//        int[] c={9,3,5,1}; //价值
        int[] w={1,3};   //重量
        int[] c={1,4}; //价值
        int capacity=7;   //容量
        System.out.println(maxKnapsack2(w,c,capacity));
    }

    /**
     * @param w
     * @param c
     * @param capacity
     * @return
     */
    public static int maxKnapsack2(int[] w,int[] c,int capacity){
//        dp[i]表示当容量为 i时 能拿到的最大值
        int[] dp=new int[capacity+1];
        for (int i = 1; i < dp.length; i++) {
            for (int n=0;n<w.length;n++){
                if (i>=w[n]){   //如果可以拿下当前物品
                    int selectCurr=dp[i-w[n]]+c[n];
                    int noSelectCurr=dp[i];
                    dp[i]=Math.max(selectCurr,noSelectCurr);
                }
            }
        }
        return dp[capacity];
    }
}
